For the convenience of the reader, the publications referred to herein are listed below. As used herein, the numerals within parentheses refer to the respective publications. The listed publications are incorporated herein by reference.    (1) D. Stephens and H. Zhang, “Implementing Distributed Packet Fair Queueing in a Scalable Switch Architecture,” Proc. IEEE INFOCOM 1998, pp. 282-290, April 1998.    (2) M. Nabeshima, “Performance evaluation of a combined input- and crosspoint-queued switch,” IEICE Trans. Commun., Vol. E83-B, No. 3, March 2000.    (3) R. Rojas-Cessa, E. Oki, and H. J. Chao, “CIXOB-k: Combined Input-Crosspoint-Output Buffered Packet Switch,” Proc. IEEE Globecom 2001, December 2001.    (4) S -T. Chuang, A. Goel, N. McKeown and B. Prabhakar, “Matching Output Queueing with a Combined Input Output Queued Switch,” IEEE JSAC, vol. 17, no. 6, pp. 1030-1039, June 1999.    (5) I. Stoica and H. Zhang, “Exact Emulation of an Output Queueing Switch by a Combined Input Output Queueing Switch,” presented at 6th IEEE/IFIP IWQoS 1998, Napa, Calif., 1998.
Packet switching devices are interconnected to create a packet switched communication network. Packet switching devices transfer data packets from the input lines, or input ports, of the device to the output lines, or output ports. A packet switch fabric provides the data paths and functionality needed to transfer the packets from the input ports to the appropriate output ports. There are a variety of architectures appropriate for a packet switching device. Output queued (OQ) packet switch architectures are generally considered the ideal architecture in terms of quality of service (QoS) support. This means that the QoS characteristics (delay, loss, throughput, etc.) given to packets in a data flow by an OQ switch architecture can be equal or better than any competing architecture. However, the OQ switch architecture can be rather expensive to build for devices with fast line rates or with many input and output ports. Thus, other less expensive designs are often desired.
An OQ packet switch can provide QoS guarantees to individual data flows or to groups of flows. In an OQ packet switch, data arriving to an input port of the switch fabric is, for example, immediately transferred to the appropriate output port. The data paths of the switch fabric support the simultaneous transfer of a packet from every input port to any output port. Packets are queued at the appropriate output ports until they leave the device. Thus, an N×N OQ switch (that is, an OQ switch with N input and N output ports) can be modeled as N separate multiplexers, one for each output port, and packets experience contention only from other packets destined for the same output. There are many packet schedulers that provide delay and throughput guarantees to data flows in a multiplexing environment. These schedulers are utilized at the output ports to produce a high-performance switch architecture.
Unfortunately, OQ switches are expensive to build for large N or for high-speed data lines. The high cost results from the fact that the memory associated with each output port must store up to N newly arrived packets and retrieve one outgoing packet in a packet time. Thus, if C represents the input and output port speed in bits/second, the memory at each output port must be able to process C×(N+1) bits/second. OQ switch architectures are generally possible for switch sizes with a total throughput, C×N, less than 60 Gbit/s.
It is possible to reduce the capacity requirements (and often the access speed requirements) of the output port memory through a switch design that combines input queueing with a limited amount of memory in the switch fabric. A fabric containing speedup requires output queueing as well. Flow-control is needed to insure the limited fabric buffers do not overflow. We refer to this architecture as a combined input, fabric and output queued (CIFOQ) switch. The Tellabs® 6400 and Tellabs® 6500 systems sold by Tellabs, Inc. of Naperville, Ill. USA, for example, have this architecture. For the CIFOQ switch, a combination of flow-control from the fabric to the line cards, sophisticated bandwidth allocation and complex scheduling at the input line cards is used to give good overall system performance. The performance, however, can often fall far short of the OQ switch. For example, various industry approaches for the CIFOQ architecture have throughput and delay guarantee limitations (see (1)-(3)).